import java.util.LinkedList;

public class constructExpressionTree {
    public static void main(String[] args) {
        String[] strs = {"2","1","-","3","*"};
        System.out.println(constructExpressionTree2(strs));

    }

    /*
    中缀表达式           (2-1)*3
    后缀（逆波兰）表达式   21-3*

    1.遇到数字入栈
    2.遇到运算符, 出栈两次, 与当前节点建立父子关系, 当前节点入栈

    栈
    |   |
    |   |
    |   |
    _____
    '-'.right = 1;
    '-'.left = 2;

    '*'.right = 3;
    '*'.left = -;
    表达式树
        *
       / \
      -   3
     / \
    2   1

    21-3*
 */
   static class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;

        TreeNode(String val) {
            this.val = val;
        }

        TreeNode(TreeNode left, String val, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val='" + val + '\'' +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
    public static TreeNode constructExpressionTree2(String[] tokens) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        for (String token : tokens) {
            switch (token) {
                case "+", "-", "*", "/" -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode parent = new TreeNode(left, token, right);
                    stack.push(parent);
                }
                default -> {
                    //数字
                    stack.offer(new TreeNode(token));

                }
            }
        }
        return stack.peek();
    }
}


